import functools
from typing import List


class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        m = len(students)
        n = len(students[0])

        # 预计算每个学生和老师的兼容性评分
        marks = [[0] * m for _ in range(m)]
        for i1 in range(m):
            for i2 in range(m):
                for j in range(n):
                    if students[i1][j] == mentors[i2][j]:
                        marks[i1][i2] += 1

        # for row in marks:
        #     print(row)

        # 将学生与老师配对
        @functools.lru_cache(None)
        def dfs(ii1, stat):
            if ii1 == m:
                return 0

            res = 0
            for ii2 in range(m):
                if not stat & (1 << ii2):
                    res = max(res, marks[ii1][ii2] + dfs(ii1 + 1, stat | (1 << ii2)))
            return res

        return dfs(0, 0)


if __name__ == "__main__":
    # 8
    print(Solution().maxCompatibilitySum(students=[[1, 1, 0], [1, 0, 1], [0, 0, 1]],
                                         mentors=[[1, 0, 0], [0, 0, 1], [1, 1, 0]]))

    # 0
    print(Solution().maxCompatibilitySum(students=[[0, 0], [0, 0], [0, 0]],
                                         mentors=[[1, 1], [1, 1], [1, 1]]))
